Digital image data must be transformed or pre-processed so that computer display terminals with various grey level capacities, laser printers, dot matrix printers, inkjet printers etc., many having different resolutions and aspect ratios, will all render an image represented by the image data in a similar way. A pre-processor associated with or configured for each such output device transforms the digital data to a form tailored to the characteristics of that particular device.
Digital halftoning is a key component of such a pre-processor. This term refers to any process that creates the illusion of continuous tone images by judicious arrangement of binary picture elements, such as ink drops in the case of inkjet printers. Digital halftoning is sometimes called spatial dithering.
Various digital halftoning techniques are known. They generally fall into one of two broad classes, depending on the type of dot created, dispersed, or clustered. If a display device can successfully accommodate an isolated black or white pixel, then by far the preferred choice is dispersed-dot halftoning, which maximizes the use of resolution. A clustered-dot halftone mimics the photoengraving process used in printing, for tiny pixels collectively form dots of various sizes.
There is also a choice of computational complexity that can be accepted. A "point operation" in image processing refers to any algorithm which produces output for a given location based only on the single input pixel at that location, independent of its neighbors. Thus, in point operations, halftoning is accomplished by a simple pointwise comparison of the input image against a predetermined threshold array or mask. For every point or pixel in the input image, depending on which point value is larger--the gray scale image or the mask--either a 1 or 0, respectively, is placed at the corresponding location in the binary output image. While various masks may be used, the general procedure for point halftoning is known. Details of such a procedure are disclosed in U.S. Pat. No. 5,111,310 to Parker, et al., said patent being incorporated herein by this reference. For applications where minimizing computation time and/or hardware is a premium, a point operation is preferred. Neighborhood operations, also called error diffusion, are more computationally intensive but generally produce higher quality results.
Dispersed-dot ordered dither (a point operation) is implemented by use of a dither matrix or threshold array, also called a mask. Hereinafter we will refer to such as a dither matrix. Halftoning with a particular homogenous dither matrix has become known as "Bayer's dither." According to Bayer's dither, methods such as recursive tessellation are used for generating optimally homogenous ordered dither matrices. According to those techniques, the goal in generating a dither matrix is to order the samples so that, as each successive position or point is numbered (turned on), the total two dimensional ensemble of "on" points remains as homogeneously arranged as possible. When matrices of this type are used as threshold arrays, the corresponding arrangement of output binary dots will be dispersed as homogeneously as possible for each gray level to be simulated.
Known ordered-dither techniques such as Bayer's dither, in some circumstances generate patterns or anomalies that appear in a rendered image in areas where the source image is of constant gray value (or nearly so). While some of these patterns are unobtrusive, and an element of subjective judgement is involved in any case, the need remains for improving output image quality in halftone systems by use of an improved dither matrix.